package leetcode.code1671;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	public int minimumMountainRemovals(int[] nums) {
		int n = nums.length;
		int[] left = lis1(nums);
		int[] right = lis2(nums);
		int ans = 100000;
		for (int i = 0; i < n; i++) {
			if (left[i] != 0 && right[i] != 0) {
				int cur = n - (left[i] + right[i] + 1);
				ans = Math.min(cur, ans);
			}
		}
		return ans;
	}

	private int[] lis1(int[] nums) {
		int n = nums.length;
		int[] ans = new int[n];
		List<Integer> dp = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int num = nums[i];
			int pos = bisect(dp, num);
			ans[i] = pos;
			if (pos == dp.size()) {
				dp.add(num);
			} else {
				dp.set(pos, num);
			}
		}
		return ans;
	}

	private int[] lis2(int[] nums) {
		int n = nums.length;
		int[] ans = new int[n];
		List<Integer> dp = new ArrayList<>();
		for (int i = n - 1; i >= 0; i--) {
			int num = nums[i];
			int pos = bisect(dp, num);
			ans[i] = pos;
			if (pos == dp.size()) {
				dp.add(num);
			} else {
				dp.set(pos, num);
			}
		}
		return ans;
	}

	public int bisect(List<Integer> dp, int num) {
		int l = 0, r = dp.size();
		while (l < r) {
			int m = ((r - l) >> 1) + l;
			if (dp.get(m) < num) {
				l = m + 1;
			} else {
				r = m;
			}
		}
		return l;
	}

//	public int bisect(List<Integer> dp, int num) {
//		int n = dp.size();
//		if (n == 0 || num < dp.get(0)) {
//			return 0;
//		}
//		if (num > dp.get(n - 1)) {
//			return n;
//		}
//		int l = 0, r = n;
//		while (l < r) {
//			int m = ((r - l) >> 1) + l;
//			if (num <= dp.get(m)) {
//				r = m;
//			} else {
//				l = m + 1;
//			}
//		}
//		return r;
//	}

	@Override
	public void debug4() {
		H.compare(6, this.minimumMountainRemovals(H.str2array3("[100,92,89,77,74,66,64,66,64]")));
		H.compare(2, this.minimumMountainRemovals(H.str2array3("[9,8,1,7,6,5,4,3,2,1]")));
		H.compare(3, this.minimumMountainRemovals(H.str2array3("[2,1,1,5,6,2,3,1]")));
		H.compare(0, this.minimumMountainRemovals(H.str2array3("[1,3,1]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		List<Integer> list = new ArrayList<>();
		list.add(1);
		list.add(5);
		list.add(7);
		list.add(12);
		list.add(15);
		System.out.println(so.bisect(list, 10));
	}

}
